package cg.studio.algorithm.list;

public class CircularList
{
  /**
   * get the entry node of the circular list, return null if it is not a circular list
   * @param firstNode
   * @return
   */
  @SuppressWarnings( "rawtypes")
  public static SNode getEntryNode( SNode firstNode )
  {
    if( firstNode == null )
      return null;
    SNode oneStep = firstNode;
    SNode twoStep = firstNode;
    
    while( twoStep != null )
    {
      oneStep = oneStep.next;
      twoStep = twoStep.next;
      if( twoStep == null )
        return null;
      twoStep = twoStep.next;
      if( twoStep == oneStep )
        break;
    }
    
    if( twoStep == null )
      return null;
    
    SNode other = firstNode;
    while( other != oneStep )
    {
      other = other.next;
      oneStep = oneStep.next;
    }
    return oneStep;
  }
}
